package chapter05_string;

import java.util.HashMap;
import java.util.Map;

/**
 * 描述：
 *      数组中两个字符串的最小距离
 *      进阶问题：如果查询发生的次数很多，如果将每次查询的时间复杂度降为O（1）
 * @author hl
 * @date 2021/8/25 21:30
 */
public class MinDistance {
    public static void main(String[] args) {
        MinDistance main = new MinDistance();
        String[] strs = {"1", "3", "3", "3", "2", "3", "1"};
        int count = main.minDistance1(strs, "1", "2");
        System.out.println(count);

        MD md = new MD(strs);
        int count2 = md.minDistance("1", "2");
        System.out.println(count2);
    }

    /**
     * 最优解
     * @param strs
     * @param str1
     * @param str2
     * @return
     */
    public int minDistance1(String[] strs, String str1, String str2){
        if (str1 == null || str2 == null) {
            return -1;
        }
        if (str1.equals(str2)) {
            return 0;
        }
        int last1 = -1;
        int last2 = -1;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].equals(str1)) {
                res = last2 == - 1 ? res : Math.min(res, i - last2);
                last1 = i;
            }
            if (strs[i].equals(str2)) {
                res = last1 == -1 ? res : Math.min(res, i - last1);
                last2 = i;
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public int minDistance2(String[] strs, String str1, String str2){
        if (str1 == null || str2 == null) {
            return -1;
        }
        if (str1.equals(str2)) {
            return 0;
        }
        Map<String, Integer> map = new HashMap<>();
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].equals(str1) && map.containsKey(str2)) {
                res = Math.min(res, i - map.get(str2));
            }
            if (strs[i].equals(str2) && map.containsKey(str1)) {
                res = Math.min(res, i - map.get(str1));
            }
            map.put(strs[i], i);
        }
        return res;
    }

    /**
     * 进阶问题，如果查询的次数很多，如果将每次查询的时间复杂度降低为O（1）
     * 引入缓存，初始化时将样本数据加载如缓存中，如何设计这个缓存的结果使得读取时间复杂度为O(1)呢？ 哈希表
     */
    public static class MD{
        private HashMap<String, HashMap<String, Integer>> record;

        public MD() {
        }

        public MD(String[] strs) {
            this.record = new HashMap<>(strs.length);
            HashMap<String, Integer> indexMap = new HashMap<>();
            HashMap<String, Integer> subMap = new HashMap<>();
            String curStr = null;
            for (int i = 0; i < strs.length; i++) {
                curStr = strs[i];
                if (!record.containsKey(curStr)) {
                    record.put(curStr, new HashMap<>());
                }
                HashMap<String, Integer> strMap = record.get(curStr);
                for (Map.Entry<String, Integer> lastEntry : indexMap.entrySet()) {
                    String lastKey = lastEntry.getKey();
                    Integer lastValue = lastEntry.getValue();
                    if (!lastKey.equals(curStr)) {
                        HashMap<String, Integer> LastMap = record.get(lastKey);
                        int curMin = i - lastValue;
                        if (strMap.containsKey(lastKey)) {
                            if(curMin < strMap.get(lastKey)){
                                strMap.put(lastKey, curMin);
                                LastMap.put(curStr, curMin);
                            }
                        }else{
                            strMap.put(lastKey, curMin);
                            LastMap.put(curStr, curMin);
                        }
                    }
                }
                indexMap.put(strs[i], i);
            }
        }
        public int minDistance(String str1, String str2){
            if (str1 == null || str2 == null) {
                return -1;
            }
            if (str1.equals(str2)) {
                return 0;
            }
            if (record.containsKey(str1) && record.get(str1).containsKey(str2)) {
                return record.get(str1).get(str2);
            }
            return  -1;
        }


    }


    public static class MD2 {
        private HashMap<String, Integer> map;
        public MD2(String[] strs) {
            map = new HashMap<>(strs.length);
            init(strs);
        }

        public MD2() {
        }

        private void init(String[] strs) {
            HashMap<String, Integer> preMap = new HashMap<>();
            String key1 = null;
            String key2 = null;
            Integer distance = 0;
            Integer preDistance = 0;
            for (int i = 0; i < strs.length; i++) {
                //更新之前存储的最短距离
                for (String m : preMap.keySet()) {
                    key1 = m + "_" + strs[i];
                    key2 = strs[i] + "_" + m;
                    distance = i - preMap.get(m);
                    //这里只存储一种str1和str2的关联关系，因此查询时需要查询两次
                    if (map.containsKey(key1)) {
                        if (map.get(key1) > distance) {
                            map.put(key1, distance);
                        }
                    }else if (map.containsKey(key2)) {
                        if (map.get(key2) > distance) {
                            map.put(key2, distance);
                        }
                    }else{
                        map.put(key1, distance);
                    }
                }
                preMap.put(strs[i], i);
            }
        }

        public int minDistance(String str1, String str2){
            if (str1 == null || str2 == null) {
                return -1;
            }
            if (str1.equals(str2)) {
                return 0;
            }
            String key1 = str1 + "_" + str2;
            String key2 = str2 + "_" + str1;
            if (map.containsKey(key1)) {
                return map.get(key1);
            }
            if (map.containsKey(key2)) {
                return map.get(key2);
            }
            return 0;
        }
    }
    
}
